package algorithm.dynamic_planning.package_learn;

/**
 * @author yuisama
 * @date 2022年12月13日 19:22
 * @description 零一背包问题
 * 给你一个可装载重量为W的背包和N个物品，其中第i个物品的重量为wt[i],价值为val[j],现在让你用这个背包装物品，求能装到的最大价值是多少
 * 这个问题中的物品不可分割，即要么物品i装进包里要么不装，不可能存在切成两半装一半，这就是0-1背包名称的由来
 */
public class ZeroAndOnePackage {
    public int knapsack(int W,int N,int[] wt,int[] val) {
        assert N == wt.length;
        // dp[i][w]对于前i个物品，当前背包的容量为w，这种情况下所能装的最大价值为dp[i][w]
        int[][] dp = new int[N + 1][W + 1];
        for (int i = 1; i <= N; i++) {
            for (int w = 1; w <= W; w++) {
                if (w - wt[i - 1] < 0) {
                    // 此时背包容量不足，只能继承前i-1个物品的最大值，不装入当前物品i
                    dp[i][w] = dp[i - 1][w];
                }else {
                    dp[i][w] = Math.max(
                            // 不装入该物品
                            dp[i - 1][w],
                            // 装入该物品
                            val[i - 1] + dp[i - 1][w - wt[i - 1]]
                    );
                }
            }
        }
        return dp[N][W];
    }
}
